package sk.fiit.lulco.grafy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import sk.fiit.lulco.gui.GraphEvent;
import sk.fiit.lulco.gui.GraphItem;
import sk.fiit.lulco.gui.GraphThread;
import sk.fiit.lulco.gui.Settings;

/**
 * class for new hybrid evolution algorithm Lulco
 */
public class NewHEALAlgorithm extends GraphThread {
	private static final GraphFitnessComparator graphFithessComparator = new GraphFitnessComparator(
			HEALConstants.SortType.DESC);

	// private static final VertexConflictsComparator vertexConflictsComparator
	// = new VertexConflictsComparator(SortType.DESC);

	public NewHEALAlgorithm(GraphItem item) {
		super(item);
	}

	@Override
	public Graph runPerformed(Graph graph) {
		Graph bestIndividual = null;
		List<Graph> generation = new ArrayList<Graph>();
		Generation nextGeneration = new Generation();
		List<Graph> newGeneration = new ArrayList<Graph>();

		RandomColoringAlgorithm randomColoring = new RandomColoringAlgorithm();
		BrelazAlgorithm brelaz = new BrelazAlgorithm();
		graph = brelaz.color(graph);
		graph.setBestColoring(graph.getColors(null).size());

//		if (graph.getBestColoring() == graph.getChromaticNumber()) {
//			return graph;
//		}

		// pre male grafy nastavime max prev colors na 1
		if (graph.getChromaticNumber() <= 10 || graph.getBestColoring() <= 10) {
			Settings.setMaxPreviousColorsSize(1);			
		}

		for (int i = 0; i < Settings.getEliteCount(); i++) {
			Graph newGraph = new Graph(graph);
			newGraph.setTimeToLive(Settings.getTimeToLive());
			generation.add(newGraph);
		}

		for (int g = 0; g < Settings.getGenerationsCount(); g++) {
			if (isCancelSet()) {
				cancelPerformed(bestIndividual, nextGeneration.getGenerationStats(), g);
				return bestIndividual;
			}

			nextGeneration.clearCache();
			nextGeneration.setNumber(g);

			if (nextGeneration.getIndividuals().size() >= Settings.getNewGenerationIndividuals()) {
				//Collections.sort(nextGeneration, graphFithessComparator);
				nextGeneration.sortIndividualsByFitness();
				nextGeneration.setIndividuals(this.subList(nextGeneration.getIndividuals(), 0, Settings.getNewGenerationIndividuals()));
			} else {
				nextGeneration.setIndividuals(this.subList(nextGeneration.getIndividuals(), 0, nextGeneration.getIndividuals().size()));
			}

			for (Graph gg : generation) {
				gg.clearFitness();
			}
			if (generation.size() >= Settings.getEliteCount()) {
				Collections.sort(generation, graphFithessComparator);
				nextGeneration.addIndividuals(this.subList(generation, 0, Settings.getEliteCount()));
			} else {
				nextGeneration.addIndividuals(this.subList(generation, 0, generation.size()));
			}
			generation.clear();
			
			Graph referer = nextGeneration.getIndividuals().size() > 0 ? nextGeneration.getBestIndividual() : (bestIndividual != null ? bestIndividual : graph);
			while (nextGeneration.getIndividuals().size() < Settings.getIndividualsInGeneration()) {
				if (isCancelSet()) {
					cancelPerformed(bestIndividual, nextGeneration.getGenerationStats(), g);
					return bestIndividual;
				}
			
				Graph newGraph = new Graph(graph.getMatrix(), graph.getChromaticNumber(), referer.getBestColoring(), graph.getInitialColors());
				newGraph.setTimeToLive(Settings.getTimeToLive());
				newGraph.setWidth(graph.getWidth());
				newGraph.setHeight(graph.getHeight());
				nextGeneration.addIndividual(randomColoring.color(newGraph));
			}

			nextGeneration.setSorted(false);
			nextGeneration.sortIndividualsByFitness();
			fireOnGraphEvent(new GraphEvent(nextGeneration.getBestIndividual(), nextGeneration.getGenerationStats(), Settings.getGenerationsCount(), g, Settings.getIndividualsInGeneration()));
			
			nextGeneration.getGenerationStats().save();
			
			StringBuilder builder = new StringBuilder();
			builder.append("generation number ");
			builder.append(g);
			builder.append("\nfinding coloring : ");
			builder.append(nextGeneration.getBestIndividual().getBestColoring());
			builder.append("\nbest individual time to live: ");
			builder.append(nextGeneration.getBestIndividual().getTimeToLive());
			builder.append("\nbest individual fitness: ");
			builder.append(nextGeneration.getBestIndividual().getFitness());
			builder.append("\nbest individual colors: ");
			builder.append(nextGeneration.getBestIndividual().getColors(null).size());
			List<Edge> conflictedEdges = nextGeneration.getBestIndividual().getConflitedEdges();
			builder.append("\nbest individual conflicted edges: ");
			builder.append(conflictedEdges.size());
			builder.append("\nbest individual conflicted vertices: ");
			builder.append(nextGeneration.getBestIndividual().getConflictedVertices(conflictedEdges).size());

			if (Settings.getGui()) {
				fireOnTextAppend(builder.toString());
			} else {
				System.out.println(builder.toString());
			}
			
			if (nextGeneration.getBestIndividual().getFitness() >= 1.0) {
				bestIndividual = new Graph(nextGeneration.getBestIndividual());
				// bestIndividual.printColors();
				int colors = bestIndividual.getColors(null).size();

				if (colors == bestIndividual.getChromaticNumber()) {
					if (Settings.getGui()) {
						fireOnTextAppend("stats saved in " + Settings.getFilename());
						Settings.setCreated(false);
					}
					return bestIndividual;
				}

				if (bestIndividual.getBestColoring() <= 11) {
					Settings.setMaxPreviousColorsSize(1);
				}
				// g = 0;
				for (Graph gr : nextGeneration.getIndividuals()) {
					gr.setBestColoring(colors - 1);
				}
			}
			Graph toCross = null;
			int k = 0;
			for (Graph graphToChange : nextGeneration.getIndividuals()) {
				if (isCancelSet()) {
					cancelPerformed(bestIndividual, nextGeneration.getGenerationStats(), g);
					return bestIndividual;
				}
				int ttl = graphToChange.getTimeToLive();
				if (ttl > 0 && generation.size() < Settings.getEliteCount()) {
					Graph saveGraph = new Graph(graphToChange);
					saveGraph.setTimeToLive(ttl - 1);
					generation.add(saveGraph);
				}

				if (toCross != null && k == nextGeneration.getIndividuals().size()) {
					newGeneration.add(this.cross(toCross, graphToChange));
					toCross = null;
				} else if (toCross == null && k == nextGeneration.getIndividuals().size()) {
					this.localSearch(graphToChange);
				} else {
					if (toCross == null) {
						toCross = graphToChange;
					} else {
						newGeneration.add(this.cross(toCross, graphToChange));
						toCross = null;
					}
				}
			}
			nextGeneration.addIndividuals(newGeneration);
			newGeneration.clear();
		}

		if (bestIndividual == null) {
			nextGeneration.setSorted(false);
			nextGeneration.sortIndividualsByFitness();
			bestIndividual = nextGeneration.getBestIndividual();

			Collections.sort(generation, graphFithessComparator);
			bestIndividual = bestIndividual.getFitness() > generation.get(0).getFitness() ? bestIndividual
					: generation.get(0);
		}
		fireOnGraphEvent(new GraphEvent(bestIndividual, null, Settings.getGenerationsCount(), Settings.getGenerationsCount(), Settings.getIndividualsInGeneration()));
		if (Settings.getGui()) {
			fireOnTextAppend("stats saved in " + Settings.getFilename());
			Settings.setCreated(false);
		}
		return bestIndividual;
	}

	private void cancelPerformed(Graph bestIndividual, GenerationStats generationStats, int g) {
		fireOnGraphEvent(new GraphEvent(bestIndividual, generationStats, Settings.getGenerationsCount(), g, Settings.getIndividualsInGeneration()));
		fireOnFinish();
		Settings.setCreated(false);
	}

	/**
	 * local search
	 * 
	 * @param	Graph	graph
	 * @return	void
	 */
	private void localSearch(Graph graph) {
		int maxColor = graph.getBestColoring();
		int newColor = 0;
		Random rand = new Random();
		double random;
		// Collections.sort(graph.getVertices(), vertexConflictsComparator);
		for (Vertex vertex : graph.getVertices()) {
			random = rand.nextDouble();
			newColor = graph.getMinimalFreeColor(vertex.getNeighbours(), null);
			if ((vertex.getConflictsCount() > 0 || vertex.getColor() > maxColor)
					&& random < Settings.getConflictedVerticesMutationProbability()) {
				if (newColor > maxColor) {
					this.clearColors(vertex, Settings.getTimeToLive() - graph.getTimeToLive());
					vertex.setColor(0);
				} else {
					vertex.setColor(newColor);
				}
			} else if (vertex.getConflictsCount() == 0
					&& random < Settings.getNonConflictedVerticesMutationProbability()) {
				this.clearColors(vertex, 1);
				vertex.setColor(0);
			}
		}

		random = rand.nextDouble();
		AbstractAlgorithm algorithm = null;
		if (random < 0.5) {
			algorithm = new BrelazAlgorithm();
		} else {
			algorithm = new TabuColoringAlgorithm();
		}

		if (algorithm != null) {
			algorithm.color(graph);
			
			// if (graph.isWellColored()) {
			// MinimizeColorAlgorithm alg = new MinimizeColorAlgorithm();
			// alg.color(graph);
			// }
		}
	}

	/**
	 * method for crossing individuals
	 * 
	 * @param Graph
	 *            graph1
	 * @param Graph
	 *            graph2
	 * @return Graph
	 */
	private Graph cross(Graph graph1, Graph graph2) {
		Random rand = new Random();

		int[] firstGraph = new int[graph1.getVertices().size() + 1];
		for (Vertex vertex : graph1.getVertices()) {
			firstGraph[vertex.getId()] = vertex.getColor();
		}

		int[] secondGraph = new int[graph2.getVertices().size() + 1];
		for (Vertex vertex : graph2.getVertices()) {
			secondGraph[vertex.getId()] = vertex.getColor();
		}

		int[] initialColors = new int[graph1.getVertices().size() + 1];
		double probability;
		for (Vertex vertex : graph1.getVertices()) {
			probability = rand.nextDouble();
			initialColors[vertex.getId()] = probability < 0.5 ? firstGraph[vertex.getId()]
					: secondGraph[vertex.getId()];
		}
		Graph newGraph = new Graph(graph1.getMatrix(), graph1.getChromaticNumber(), graph1.getBestColoring(),
				initialColors);
		newGraph.setTimeToLive(Settings.getTimeToLive());
		newGraph.setWidth(graph1.getWidth());
		newGraph.setHeight(graph1.getHeight());

		this.localSearch(graph1);
		this.localSearch(graph2);
		this.localSearch(newGraph);
		return newGraph;
	}

	/**
	 * getter for maximal previous color array size
	 * 
	 * @return int
	 */
	public static int getMaxPreviousColorsSize() {
		return Settings.getMaxPreviousColorsSize();
	}

	/**
	 * own method for create sublist of list
	 * 
	 * @param List
	 *            <Graph> originalList
	 * @param int indexFrom
	 * @param int indexTo
	 * @return List<Graph>
	 */
	private List<Graph> subList(List<Graph> originalList, int indexFrom, int indexTo) {
		List<Graph> list = new ArrayList<Graph>();
		for (int i = indexFrom; i < indexTo; i++) {
			list.add(originalList.get(i));
		}
		return list;
	}

	/**
	 * method for clearing colors of vertex and its neighbours recursively
	 * 
	 * @param Vertex
	 *            vertex
	 * @param int distance
	 * @return void
	 */
	private void clearColors(Vertex vertex, int distance) {
		if (distance > 0) {
			for (Vertex neighbour : vertex.getNeighbours()) {
				if (neighbour.getColor() != 0) {
					neighbour.setColor(0);
					this.clearColors(neighbour, distance - 1);
				}
			}
		}
	}
}